GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Eulerkreisproblem</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Eulerkreisproblem</h1>

</header>

</div>

Ein Eulerkreis (auch geschlossener Eulerzug, Eulertour) ist in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> ein <a href="Zyklus_(Graphentheorie)" title="Zyklus (Graphentheorie)">Zyklus</a>, der alle <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> eines <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a> genau einmal enthält.

Ein offener Eulerzug (auch Eulerpfad oder Eulerweg) ist gegeben, wenn Start- und Endknoten nicht gleich sein müssen, wenn also statt eines <a href="Zyklus_(Graphentheorie)" title="Zyklus (Graphentheorie)">Zyklus</a> lediglich eine <a href="Weg_(Graphentheorie)" title="Weg (Graphentheorie)">Kantenfolge</a> verlangt wird, welche jede Kante des Graphen genau einmal enthält. Ein bekanntes Beispiel ist das „<a href="#Das_Haus_vom_Nikolaus">Haus vom Nikolaus</a>“.

Ein <a href="Zusammenh%C3%A4ngender_Graph" class="mw-redirect" title="Zusammenhängender Graph">zusammenhängender Graph</a>, der einen Eulerkreis besitzt, heißt eulerscher Graph. Enthält ein Graph lediglich einen Eulerweg und keinen Eulerkreis, so heißt er semi-eulerscher Graph. Die Aufgabe, zu einem gegebenen Graph zu bestimmen, ob dieser eulersch ist oder nicht, wird als Eulerkreisproblem bezeichnet. Es geht auf das 1736 von <a href="Leonhard_Euler" title="Leonhard Euler">Leonhard Euler</a> gelöste <a href="K%C3%B6nigsberger_Br%C3%BCckenproblem" title="Königsberger Brückenproblem">Königsberger Brückenproblem</a> zurück. Das Problem existiert auch für <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichtete Graphen</a> und <a href="Graph_mit_Mehrfachkanten" class="mw-redirect" title="Graph mit Mehrfachkanten">Graphen mit Mehrfachkanten</a>.

Entgegen seinem Namen ist der Eulerkreis kein <a href="Kreis_(Graphentheorie)" class="mw-redirect" title="Kreis (Graphentheorie)">Kreis</a>, zumindest wenn der häufigen Definition gefolgt wird, nach der sich in einem Kreis kein <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> wiederholen darf.

<div class="mw-heading mw-heading2"><h2 id="Geschichte">Geschichte</h2></div>

Leonhard Euler fragte in seiner Arbeit 1736 zum Königsberger Brückenproblem – übersetzt in die heutige Fachsprache –, ob der durch die <a href="Pregel" title="Pregel">Pregelbrücken</a> der Stadt gegebene Graph ein semi-eulerscher Graph ist, das heißt, ob ein Eulerweg existiert, und verneinte dies, da der Graph mehr als zwei Knoten mit ungeradem Grad hatte. Euler bewies, dass ein semi-eulerscher Graph höchstens zwei Knoten ungeraden <a href="Grad_(Graphentheorie)" title="Grad (Graphentheorie)">Grades</a> haben kann.<a href="#cite_note-1">[1]</a> Er vermutete und gab ohne Beweis an, dass dies eine hinreichende Bedingung sei: Ein zusammenhängender Graph, in dem jeder Knoten geraden Grad hat, ist ein Eulergraph. Ein Beweis des Satzes wurde zuerst von <a href="Carl_Hierholzer" title="Carl Hierholzer">Carl Hierholzer</a> 1873 veröffentlicht.<a href="#cite_note-2">[2]</a> Auf dem Beweis basiert der <a href="Algorithmus_von_Hierholzer" title="Algorithmus von Hierholzer">Algorithmus von Hierholzer</a> zum Auffinden eines Eulerwegs.

<div class="mw-heading mw-heading2"><h2 id="Charakterisierung">Charakterisierung</h2></div>

Nach dem Satz von Euler-Hierholzer sind eulersche Graphen leicht zu charakterisieren.

Sei G ein Graph, bei dem höchstens eine Zusammenhangskomponente Kanten enthält. Dann sind folgende Aussagen äquivalent:

<ol><li>G ist eulersch,</li>

<li>jeder Knoten in G hat <a href="Parit%C3%A4t_(Mathematik)" title="Parität (Mathematik)">geraden</a> Grad.</li>

<li>die Kantenmenge von G ist die <a href="Vereinigungsmenge" class="mw-redirect" title="Vereinigungsmenge">Vereinigungsmenge</a> aller Kanten von <a href="Paarweise_disjunkt" class="mw-redirect" title="Paarweise disjunkt">paarweise disjunkten</a> Kreisen.</li></ol>

Analog sind für einen <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteten Graphen</a> G, bei dem höchstens eine <a href="Zusammenhang_(Graphentheorie)#Gerichtete_Graphen" title="Zusammenhang (Graphentheorie)">starke Zusammenhangskomponente</a> Kanten enthält, folgende Aussagen äquivalent:

<ol><li>G ist eulersch,</li>

<li>für jeden Knoten in G sind <a href="Eingangsgrad" class="mw-redirect" title="Eingangsgrad">Eingangsgrad</a> und <a href="Ausgangsgrad" class="mw-redirect" title="Ausgangsgrad">Ausgangsgrad</a> gleich.</li>

<li>die Kantenmenge von G ist die <a href="Vereinigungsmenge" class="mw-redirect" title="Vereinigungsmenge">Vereinigungsmenge</a> aller Kanten von paarweise disjunkten <a href="Gerichteter_Kreis" class="mw-redirect" title="Gerichteter Kreis">gerichteten Kreisen</a>.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Verallgemeinerung:_Eulerweg">Verallgemeinerung: Eulerweg</h2></div>

Ein <a href="Ungerichteter_Graph" class="mw-redirect" title="Ungerichteter Graph">ungerichteter</a> <a href="Zusammenh%C3%A4ngender_Graph" class="mw-redirect" title="Zusammenhängender Graph">zusammenhängender Graph</a> enthält <a href="Genau_dann%2C_wenn" class="mw-redirect" title="Genau dann, wenn">genau dann</a> einen Eulerweg, wenn zwei oder keiner seiner Knoten von ungeradem Grad sind. Hat kein Knoten einen ungeraden Grad, handelt es sich bei jedem Eulerweg um einen Eulerkreis.

<div class="mw-heading mw-heading2"><h2 id="Entscheidungsproblem">Entscheidungsproblem</h2></div>

Die Frage, ob für einen gegebenen Graph ein Eulerkreis existiert, lässt sich algorithmisch relativ leicht lösen, da ein Graph genau dann eulersch ist, wenn er <a href="Zusammenh%C3%A4ngender_Graph" class="mw-redirect" title="Zusammenhängender Graph">zusammenhängend</a> ist und jeder Knoten geraden Grad besitzt. Mittels <a href="Tiefensuche" title="Tiefensuche">Tiefensuche</a> lässt sich dies leicht in linearer Zeit feststellen.

<div class="mw-heading mw-heading2"><h2 id="Auffinden_eines_Eulerkreises">Auffinden eines Eulerkreises</h2></div>

Zum Auffinden eines Eulerkreises existieren mehrere Verfahren. Der Algorithmus von Fleury stammt aus dem Jahr 1883 und verfolgt einen sehr einfachen Ansatz, weshalb er eine <a href="Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeit</a> von der Größenordnung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|E|^{2})}">

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|E|^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af06b6a1c146f14ab500cc06e27b47eb0e5d3594.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.783ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}(|E|^{2})}" loading="lazy"> hat.

Effizienter ist der <a href="Algorithmus_von_Hierholzer" title="Algorithmus von Hierholzer">Algorithmus von Hierholzer</a>, der einen Eulerkreis in Linearzeit berechnet.

<div class="mw-heading mw-heading3"><h3 id="Algorithmus_von_Fleury">Algorithmus von Fleury</h3></div>

Im Algorithmus von Fleury spielen Brückenkanten eine wichtige Rolle. Das sind Kanten, ohne die der Graph in zwei Komponenten zerfallen würde.

Der Algorithmus fügt einer anfangs leeren Kantenfolge alle Kanten eines Graphen hinzu, sodass ein Eulerkreis entsteht.

<ol><li>Wähle einen beliebigen Knoten als aktuellen Knoten.</li>

<li>Wähle unter den unmarkierten, mit dem aktuellen Knoten inzidenten Kanten eine beliebige Kante aus. Dabei sind zuerst Kanten zu wählen, die im unmarkierten Graphen keine Brückenkanten sind.</li>

<li>Markiere die gewählte Kante und füge sie der Kantenfolge hinzu.</li>

<li>Wähle den anderen Knoten der gewählten Kante als neuen aktuellen Knoten.</li>

<li>Wenn noch unmarkierte Kanten existieren, dann gehe zu Schritt 2.</li></ol>

Ob eine Kante eine Brückenkante ist, kann mittels <a href="Tiefensuche" title="Tiefensuche">Tiefensuche</a> in Laufzeit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|E|)}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|E|)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/969a8859cbc34a826fcf95b2224e73dad27bee4e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.729ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(|E|)}" loading="lazy"> überprüft werden. Da pro Schritt eine Kante entfernt wird, werden <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left|E\right|}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left|E\right|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b8281fbfd0b61f0eb5f2f877bffe92f02cc732d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.069ex; height:2.843ex;" alt="{\displaystyle \left|E\right|}" loading="lazy"> Iterationen benötigt. Die Anzahl der pro Iteration geprüften Kanten entspricht dem Grad des aktuellen Knotens. Insgesamt kann die gesamte Anzahl überprüfter Kanten durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|E|)}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|E|)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/969a8859cbc34a826fcf95b2224e73dad27bee4e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.729ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(|E|)}" loading="lazy"> beschränkt werden. Die gesamte Laufzeit ist damit von der Größenordnung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(|E|^{2})}">

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(|E|^{2})}</annotation>

</semantics>

<div class="mw-heading mw-heading4"><h4 id="Programmierung">Programmierung</h4></div>

Das folgende Beispiel in der <a href="Programmiersprache" title="Programmiersprache">Programmiersprache</a> <a href="C-Sharp" title="C-Sharp">C#</a> zeigt die Implementierung des Algorithmus von Fleury für einen <a href="Ungerichteter_Graph" class="mw-redirect" title="Ungerichteter Graph">ungerichteten Graphen</a>. Der ungerichtete Graph wird als <a href="Klasse_(Objektorientierung)" title="Klasse (Objektorientierung)">Klasse</a> UndirectedGraph deklariert. Bei der Ausführung des Programms wird die <a href="Methode_(Programmierung)" title="Methode (Programmierung)">Methode</a> Main verwendet, die den Eulerkreis oder Eulerpfad auf der Konsole ausgibt.<a href="#cite_note-:0-3">[3]</a>

<td style="text-align:left; font-size: 95%;">Code-Schnipsel

</td></tr>

<tr>

<td>

<div class="mw-highlight mw-highlight-lang-c# mw-content-ltr" dir="ltr"><pre>using System;

using System.Collections.Generic;

// Deklariert die Klasse für die Knoten des Graphen

class Node

{

public int index;

public string value;

public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Menge der Nachbarknoten

}

// Deklariert die Klasse für den ungerichteten Graphen

class UndirectedGraph

{

public HashSet<Node> nodes = new HashSet<Node>();

// Diese Methode verbindet die Knoten node1 und node2 miteinander.

public void ConnectNodes(Node node1, Node node2)

{

node1.adjacentNodes.Add(node2);

node2.adjacentNodes.Add(node1);

}

// Diese Methode trennt die Knoten node1 und node2 voneinander.

public void DisconnectNodes(Node node1, Node node2)

{

node1.adjacentNodes.Remove(node2);

node2.adjacentNodes.Remove(node1);

}

}

class Program

{

// Diese Methode gibt die Eulerpfad, die als Liste von Knoten übergeben wird, in der Form (A, B), (B, C), (C, D), ... als Text zurück.

public static string EulerPathToString(List<Node> nodeList)

{

string text = "";

for (int i = 0; i < nodeList.Count - 1; i++) // for-Schleife, die die Knoten durchläuft

{

text += "(" + nodeList[i].value + ", " + nodeList[i + 1].value + "), ";

}

text = text.Substring(0, text.Length - 2);

return text;

}

// Diese Methode gibt die Liste der durchlaufenen Knoten zurück

public static List<Node> GetEulerPathByFleury(UndirectedGraph undirectedGraph, Node startNode)

{

// Behandelt den Fall, dass es zwei Knoten mit ungeradem Grad gibt und sucht einen Knoten mit ungeradem Grad

foreach (Node node in undirectedGraph.nodes) // foreach-Schleife, die alle Knoten des Graphen durchläuft

{

if (node.adjacentNodes.Count % 2 == 1) // Wenn der Grad des aktuellen Knoten ungerade ist

{

startNode = node; // Knoten als Startknoten auswählen und foreach-Schleife verlassen

break;

}

List<Node> nodeList = new List<Node>(); // Initialisiert die Liste der durchlaufenen Knoten

Node nextNode = null; // Referenz auf den jeweils nächsten Knoten der Eulerpfad, die gegebenenfalls nach dem vollständigen Durchlaufen der Kanten für den letzten Knoten (Zielknoten) benötigt wird.

AddNextEulerPathNode(undirectedGraph, startNode, ref nextNode, nodeList); // Aufruf der rekursiven Methode, die jeweils den nächsten Knoten hinzufügt

if (nextNode != null)

{

nodeList.Add(nextNode); // Wenn Referenz nicht null, Zielknoten hinzufügen

}

return nodeList;

}

// Rekursive Methode, die jeweils den nächsten Knoten hinzufügt

private static void AddNextEulerPathNode(UndirectedGraph undirectedGraph, Node startNode, ref Node nextNode, List<Node> nodeList)

{

HashSet<Node> adjacentNodes = new HashSet<Node>(startNode.adjacentNodes);

{

if (startNode.adjacentNodes.Contains(node) && IsValidNextEdge(undirectedGraph, startNode, node))

{

nextNode = node;

nodeList.Add(startNode);

undirectedGraph.DisconnectNodes(startNode, node);

AddNextEulerPathNode(undirectedGraph, node, ref nextNode, nodeList); // Rekursiver Aufruf der Methode

}

// Diese Methode prüft, ob sich mit der aktuellen Kante die Eulerpfad vervollständigen lässt

private static bool IsValidNextEdge(UndirectedGraph undirectedGraph, Node node1, Node node2)

{

if (node1.adjacentNodes.Count == 1 && node1.adjacentNodes.Contains(node2))

{

return true;

}

HashSet<Node> visitedNodes = new HashSet<Node>();

DepthFirstSearch(node1, visitedNodes);

int count1 = visitedNodes.Count;

undirectedGraph.DisconnectNodes(node1, node2);

visitedNodes.Clear();

int count2 = visitedNodes.Count;

undirectedGraph.ConnectNodes(node1, node2);

return count1 == count2;

}

// Diese Methode verwendet Tiefensuche, um alle erreichbaren Knoten des Graphen zu durchlaufen

{

visitedNodes.Add(startNode); // Fügt den aktuellen Knoten der Menge der markierten Knoten hinzu

foreach (Node node in startNode.adjacentNodes) // foreach-Schleife, die alle benachbarten Knoten des Knotens durchläuft

{

if (!visitedNodes.Contains(node)) // Wenn der Knoten noch nicht markiert wurde

{

DepthFirstSearch(node, visitedNodes); // Rekursiver Aufruf der Methode mit dem Nachbarknoten als Startknoten

}

// Hauptmethode, die das Programm ausführt

public static void Main()

{

// Deklariert und initialisiert 5 Knoten

Node node1 = new Node{index = 0, value = "A"};

Node node2 = new Node{index = 1, value = "B"};

Node node3 = new Node{index = 2, value = "C"};

Node node4 = new Node{index = 3, value = "D"};

Node node5 = new Node{index = 4, value = "E"};

// Deklariert und initialisiert ein Array mit den Knoten

Node[] nodes = {node1, node2, node3, node4, node5};

// Erzeugt einen ungerichteten Graphen

UndirectedGraph undirectedGraph = new UndirectedGraph();

int numberOfNodes = nodes.Length;

for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten durchläuft

{

undirectedGraph.nodes.Add(nodes[i]); // Fügt die Knoten dem Graphen hinzu

}

// Verbindet Knoten des Graphen miteinander

undirectedGraph.ConnectNodes(node2, node1);

undirectedGraph.ConnectNodes(node3, node2);

undirectedGraph.ConnectNodes(node4, node5);

undirectedGraph.ConnectNodes(node4, node3);

undirectedGraph.ConnectNodes(node4, node2);

undirectedGraph.ConnectNodes(node3, node5);

List<Node> eulerPath = GetEulerPathByFleury(undirectedGraph, node1); // Aufruf der Methode, die die Liste der durchlaufenen Knoten zurückgibt

if (eulerPath.Count == 9) // Wenn die Anzahl der durchlaufenen Knoten um 1 größer als die Anzahl aller Kanten ist

{

string eulerPathText = EulerPathToString(eulerPath); // Aufruf der Methode

Console.WriteLine(eulerPathText); // Ausgabe auf der Konsole

}

else

{

Console.WriteLine("Es existiert kein Eulerpfad."); // Ausgabe auf der Konsole

}

Console.ReadLine();

}

}

</pre></div>

</td></tr></tbody></table>

Hinweise: Sowohl für das <a href="Referenz_(Programmierung)" title="Referenz (Programmierung)">Referenzieren</a> der <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> des <a href="Ungerichteter_Graph" class="mw-redirect" title="Ungerichteter Graph">ungerichteten Graphen</a> als auch für das Referenzieren der <a href="Nachbarknoten" class="mw-redirect" title="Nachbarknoten">Nachbarknoten</a> jedes Knoten wird ein HashSet (<a href="Menge_(Datenstruktur)" title="Menge (Datenstruktur)">Menge</a>) als <a href="Datentyp" title="Datentyp">Datentyp</a> verwendet und mit <a href="Foreach-Schleife" class="mw-redirect" title="Foreach-Schleife">foreach-Schleifen</a> durchlaufen. Der Vorteil des HashSet für die Nachbarknoten im Vergleich zu einer <a href="Liste_(Datenstruktur)" title="Liste (Datenstruktur)">Liste</a> ist, dass dann meist viel schneller, nämlich mit konstanter <a href="Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeit</a>, geprüft werden kann, ob ein bestimmter Knoten Nachbarknoten eines anderen Knoten ist (siehe <a href="Hashtabelle#Vorteile_2" title="Hashtabelle">Hashtabelle – Vorteile</a>). Ein Nachteil ist, dass dann die <a href="Reihenfolge" title="Reihenfolge">Reihenfolge</a> der durchlaufenen Knoten in den <a href="Foreach-Schleife" class="mw-redirect" title="Foreach-Schleife">foreach-Schleifen</a> und damit auch die Reihenfolge der ausgegebenen Knoten des Eulerpfads nicht <a href="Eindeutigkeit" title="Eindeutigkeit">eindeutig</a> oder teilweise <a href="Zufall" title="Zufall">zufällig</a> ist.

Im Programmbeispiel wird nur einer der möglichen Eulerpfade bestimmt und ausgegeben, falls einer existiert.

Statt dem HashSet (<a href="Menge_(Datenstruktur)" title="Menge (Datenstruktur)">Menge</a>) visitedNodes kann auch eine <a href="Liste" title="Liste">Liste</a> oder ein <a href="Feld_(Datentyp)" class="mw-redirect" title="Feld (Datentyp)">Array</a> vom Typ bool (<a href="Boolesche_Variable" class="mw-redirect" title="Boolesche Variable">Boolesche Variable</a>) verwendet werden, wie im Einzelnachweis gezeigt.<a href="#cite_note-:0-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Vermutung_von_Hajos">Vermutung von Hajos</h2></div>

Nach der im Allgemeinen ungelösten Zyklenvermutung von <a href="Gy%C3%B6rgy_Haj%C3%B3s" title="György Hajós">György Hajós</a> über Kreiszerlegung von <a href="Eulergraph" class="mw-redirect" title="Eulergraph">Eulergraphen</a> von 1968 können Eulergraphen mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Knoten in höchstens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{2}}(n-1)}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{2}}(n-1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/736bdc8316a73a5999d5507534631be652a05e36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:9.205ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{2}}(n-1)}" loading="lazy"> Kreise zerlegt werden. Die Vermutung wurde für kleine Graphen (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\leq 12}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\leq 12}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ced0c8199572399fda990e12bbbbc5192f3c0cae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.818ex; height:2.343ex;" alt="{\displaystyle n\leq 12}" loading="lazy">) 2017 bewiesen<a href="#cite_note-4">[4]</a> und für <a href="Pfadweite" title="Pfadweite">Pfadweite</a> kleiner oder gleich 6.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Anwendungsbeispiele">Anwendungsbeispiele</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Das_Königsberger_Brückenproblem">Das Königsberger Brückenproblem</h3></div>

Das <a href="K%C3%B6nigsberger_Br%C3%BCckenproblem" title="Königsberger Brückenproblem">Königsberger Brückenproblem</a> lässt sich in folgendem Graphen ausdrücken:

Die Kreise (<a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a>) sind die jeweiligen Stadtteile bzw. Standpunkte. Die Linien (<a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a>) sind die Brücken. Durch Probieren wird herausgefunden, dass es nicht möglich ist, einen Rundgang durch die Stadt zu finden, bei dem jede Brücke genau ein einziges Mal benutzt wird. Es gibt also keinen Eulerweg und demzufolge auch keinen Eulerkreis. Warum ist das so?

Euler hat die folgende Gesetzmäßigkeit entdeckt: Wenn in einem Graphen G ein Eulerweg existiert, dann haben maximal 2 Knoten ungeraden Grad. Beim Königsberger Brückengraphen gibt es vier Knoten mit ungeradem Grad. Die Zahlen neben den Knoten geben in der Abbildung deren Grad an. Deshalb ist der Stadtrundgang mit dem nur einmaligen Benutzen jeder Brücke unmöglich.

Ein ungerader Knoten ist entweder Anfang oder Ende des Weges über die Brücken: null ungerade Knoten würde bedeuten, dass Anfang und Ende des Weges in Königsberg identisch sind. Ein Weg mit Anfang und Ende hätte maximal zwei ungerade Knoten. Ergo ist es in Königsberg nicht möglich gewesen, alle Brücken in einem Wege nur jeweils einmal zu begehen.

<div class="mw-heading mw-heading3"><h3 id="Das_Haus_vom_Nikolaus">Das Haus vom Nikolaus</h3></div>

<div class="hauptartikel" role="navigation">→ Hauptartikel: <a href="Haus_vom_Nikolaus" title="Haus vom Nikolaus">Haus vom Nikolaus</a></div>

Das beliebte Kinderrätsel „Das ist das Haus vom Nikolaus“ hingegen enthält einen Eulerweg, aber keinen Eulerkreis, da sein Graph zwei Knoten vom Grad 3 enthält.

Solch ein Eulerweg ist 1-2-4-3-1-4-5-3-2. Knoten 1 und 2 haben jeweils 3 Nachbarn, ihr Grad ist also ungerade. Um das Haus in einem Zug zeichnen zu können, muss daher an einem dieser beiden Punkte begonnen werden. Ein Quadrat mit Diagonalen enthält keinen Eulerweg, da alle seine Knoten den Grad 3 haben. Im Bild sind das nur die Punkte 1, 2, 3, 4 mit den verbindenden Kanten.

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a class="external text" href="https://commons.wikimedia.org/wiki/Category:Eulerian_paths?uselang=de">Commons: Eulerkreisproblem</a> – Sammlung von Bildern, Videos und Audiodateien</div>

<ul><li><a href="Hamiltonkreisproblem" title="Hamiltonkreisproblem">Hamiltonkreisproblem</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Wladimir Velminski: Leonhard Euler. Die Geburt der Graphentheorie. Kulturverlag Kadmos, Berlin 2008, ISBN 978-3-86599-056-3.</li>

<li>Reinhard Diestel: <a rel="nofollow" class="external text" href="https://www.math.uni-hamburg.de/home/diestel/books/graphentheorie/">Graphentheorie.</a> 3. Auflage. Springer, 2006, ISBN 3-540-21391-0, S. 23–24</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Brian Hopkins, Robin J. Wilson: <cite style="font-style:italic">The Truth about Königsberg</cite>. In: <cite style="font-style:italic">The College Mathematics Journal</cite>. Band 35, Nr. 3, 2004, Paragraphen 20 und 21, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080/07468342.2004.11922073">10.1080/07468342.2004.11922073</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Eulerkreisproblem&rft.atitle=The+Truth+about+K%C3%B6nigsberg&rft.au=Brian+Hopkins%2C+Robin+J.+Wilson&rft.date=2004&rft.doi=10.1080%2F07468342.2004.11922073&rft.genre=journal&rft.issue=3&rft.jtitle=The+College+Mathematics+Journal&rft.volume=35" style="display:none">

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Hierholzer Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren, Mathematische Annalen, Bd. 6, 1873, S. 30–32, <a rel="nofollow" class="external text" href="https://zenodo.org/record/1447429/files/article.pdf">Online</a>

</li>

<li id="cite_note-:0-3">↑ <a href="#cite_ref-:0_3-0">a</a> <a href="#cite_ref-:0_3-1">b</a> GeeksforGeeks: <a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/fleurys-algorithm-for-printing-eulerian-path/">Fleury’s Algorithm for printing Eulerian Path or Circuit</a>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> <a rel="nofollow" class="external text" href="https://arxiv.org/abs/1705.08724">Irene Heinrich, Marco Natale, Manuel Streicher, Hajós' cycle conjecture for small graphs</a>, Arxiv 2017

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> <a rel="nofollow" class="external text" href="https://arxiv.org/abs/1705.07066">Elke Fuchs, Laura Gellert, Irene Heinrich: Cycle decompositions of pathwidth-6 graphs</a>, Arxiv 2017

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-12-14" href="https://de.wikipedia.org/wiki/?title=Eulerkreisproblem&oldid=262422070">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>